package wtx.geek;

import java.util.*;
import java.util.Random;

/**
 * 给你一个字符串 s，请你对 s 的子串进行检测。
 *
 * 每次检测，待检子串都可以表示为 queries[i] = [left, right, k]。我们可以 重新排列 子串 s[left], ..., s[right]，并从中选择 最多 k 项替换成任何小写英文字母。 
 *
 * 如果在上述检测过程中，子串可以变成回文形式的字符串，那么检测结果为 true，否则结果为 false。
 *
 * 返回答案数组 answer[]，其中 answer[i] 是第 i 个待检子串 queries[i] 的检测结果。
 *
 * 注意：在替换时，子串中的每个字母都必须作为 独立的 项进行计数，也就是说，如果 s[left..right] = "aaa" 且 k = 2，我们只能替换其中的两个字母。
 * （另外，任何检测都不会修改原始字符串 s，可以认为每次检测都是独立的）
 *  
 *
 * 示例：
 *
 * 输入：s = "abcda", queries = [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]
 * 输出：[true,false,false,true,true]
 * 解释：
 * queries[0] : 子串 = "d"，回文。
 * queries[1] : 子串 = "bc"，不是回文。
 * queries[2] : 子串 = "abcd"，只替换 1 个字符是变不成回文串的。
 * queries[3] : 子串 = "abcd"，可以变成回文的 "abba"。 也可以变成 "baab"，先重新排序变成 "bacd"，然后把 "cd" 替换为 "ab"。
 * queries[4] : 子串 = "abcda"，可以变成回文的 "abcba"。
 *
 */

public class Solution {
    public List<Boolean> canMakePaliQueries(String s, int[][] queries) {
        List<Map<Character, Integer>> charInvertCount = new ArrayList<>();
        int i = 0;
        char[] charArray = s.toCharArray();
        for (char c : charArray) {
            Map<Character, Integer> curCount = new HashMap<>();
            if (!charInvertCount.isEmpty()) {
                curCount = new HashMap<>(charInvertCount.get(i-1));
            }
            curCount.merge(c, 1, (x, y) ->  x + y);
            charInvertCount.add(curCount);
            ++i;
        }
        final int QueryCount = queries.length;
        Map<Integer, Map<Integer, Integer>> resultCache = new HashMap<>();
        List<Boolean> ret = new ArrayList<>();
        for (int j = 0; j < QueryCount; ++j) {
            int[] q = queries[j];
            Map<Integer, Integer> ent = resultCache.computeIfAbsent(q[0], k -> new HashMap<>());
            if (resultCache.containsKey(q[0])) {
                int minResult = ent.getOrDefault(q[1], -1);
                if (minResult != -1) {
                    if (minResult <= q[2]) {
                        ret.add(true);
                        continue;
                    }
                }
            }
            char c = charArray[q[0]];
            Map<Character, Integer> charCount = charInvertCount.get(q[0]);
            Map<Character, Integer> charCount2 = new HashMap<>(charInvertCount.get(q[1]));
            int qn = q[1] - q[0] + 1;
            int oddNum = 0, evenNum = 0;
            for (Map.Entry<Character, Integer> e : charCount2.entrySet()) {
                e.setValue(c == e.getKey() ? (e.getValue() - charCount.get(c) + 1) :
                        e.getValue() - charCount.getOrDefault(e.getKey(), 0));
                if (e.getValue() > 0) {
                    if (e.getValue() % 2 == 0) {
                        evenNum++;
                    } else {
                        oddNum++;
                    }
                }
            }
            int k = q[2];
            if (qn % 2 == 0) {
                if (oddNum <= 2*k) {
                    ret.add(true);
                } else {
                    ret.add(false);
                }
            } else {
                if (oddNum - 1 <= 2*k) {

                    ret.add(true);
                } else {
                    ret.add(false);
                }
            }
        }
        return ret;
    }
    public static void main(String[] args) {
        Random rnd = new Random(1263);
        Solution s = new Solution();
        for (int n = 0; n < 100; ++n) {
            final int arrayLen = rnd.nextInt(10) + 10;
            char[] array = new char[arrayLen];
            for (int k = 0; k < arrayLen; ++k) {
                int c = rnd.nextInt(26) + 'a';
                array[k] = (char) c;
            }
            String str = new String(array);
            System.out.println("input string :" + str);
            int[][] queries = new int[10][3];
            for (int q = 0; q < 10; ++q) {
                int[] query = new int[3];
                query[0] = rnd.nextInt(arrayLen * 4/5);
                query[1] = rnd.nextInt(arrayLen - query[0]) + query[0];
                query[2] = rnd.nextInt(query[1] - query[0] + 1);
                queries[q] = query;
            }
            List<Boolean> ret = s.canMakePaliQueries(str, queries);
            for (int i = 0; i < 10; ++i) {
                int[] query = queries[i];
                System.out.println(String.format("range = [%d, %d], k = %d, pali-query = %b", query[0],
                        query[1], query[2], ret.get(i)));
            }
        }
    }
}
